// 32.最长有效括号
package Leetcode_Second_Brush;

public class Solution032 {
    public int longestValidParentheses(String s) {
        int length = s.length();

        if (length == 0)
            return 0;

        // dp[i] 表示以第 i 个字符结尾的最长有效括号
        int[] dp = new int[length];

        dp[0] = 0;

        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == '(')
                dp[i] = 0;
            else {
                if (s.charAt(i - 1) == '(')
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                else {
                    if (i - dp[i - 1] - 1 < 0)
                        dp[i] = 0;
                    else {
                        if (s.charAt(i - dp[i - 1] - 1) == ')')
                            dp[i] = 0;
                        else {
                            dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 : dp[i - 1] + 2;
                        }
                    }
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < length; i++) {
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}
